package com.chenxys.algorithm.newbie;

import java.util.Stack;

/**
 * <p>
 *      用链表实现栈
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/28/23 12:28 AM
 * @Copyright ©
 */
public class StackByList {
    /**
     * <p>
     *     栈节点的数据结构
     * </p>
     * @param <V>
     */
    public static class Node<V> {
        public V value;
        public Node<V> next;

        public Node(V value) {
            this.value = value;
            this.next = null;
        }
    }

    public static class MyStack<V> {
        // 头指针
        private Node<V> head;
        // 栈大小
        private int size;

        // 初始化全为空
        public MyStack() {
            head = null;
            size = 0;
        }

        // 判断栈是否为空
        public boolean isEmpty() {
            return size == 0;
        }

        // 获取栈大小
        public int size() {
            return size;
        }

        /**
         * <p>
         *     将元素押入栈
         * </p>
         * @param value 待进栈元素
         */
        public void push(V value){
            Node<V> cur = new Node<>(value);
            // 头指针为空,则将头指针指向当前节点
            if (head == null){
                head = cur;
            } else {
                // 头指针不为空,将当前节点的下一个节点指向头指针,并将头指针移动到当前节点
                cur.next = head;
                head = cur;
            }
            // 栈大小+1
            size++;
        }

        /**
         * <p>
         *     从栈中弹出一个元素
         * </p>
         * @return 弹出最后入栈的元素
         */
        public V pop(){
            V ans = null;
            // 头指针不指向空,将头指针指向的节点赋值给ans,并将头指针指向当前节点的下一个节点,栈大小-1
            if (head != null){
                ans = head.value;
                head = head.next;
                size--;
            }
            return ans;
        }

        /**
         * <p>
         *     获取最后入栈的元素值,不删除
         * </p>
         * @return 最后入栈的元素值
         */
        public V peek() {
            return head != null ? head.value : null;
        }
    }

    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        Stack<Integer> test = new Stack<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("Test Begin！");
        for (int i = 0; i < testTime; i++) {
            if (myStack.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myStack.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myStack.push(num);
                test.push(num);
            } else if (decide < 0.66) {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.pop();
                    int num2 = test.pop();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }

        System.out.println("Test Finish!");
    }
}
